package com.cuz.hot100;

public class Q53maximumSubarraySum {

    public static void main(String[] args) {
//[]
//        int[] ints = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
//        int[] ints = {1};
//        int[] ints = {5,4,-1,7,8};
//        int[] ints = {-1};
        int[] ints = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        System.out.println(maxSubArray2(ints));
        System.out.println(maxSubArray3(ints));
    }

    public static int maxSubArray1(int[] nums) {
        return process(nums, nums.length - 1);
    }

    /***
     *
     * @param nums
     * @param index index 之前连续数组 最大和是多少
     * @return
     */
    private static int process(int[] nums, int index) {
        if (index == 0) {
            return Math.max(nums[index], 0);
        }
        return process(nums, index - 1) + Math.max(nums[index], 0);
    }
    public static int maxSubArray3(int[] nums) {
        int maxSum=nums[0];
        int preSum=0;
        for (int num : nums) {
            preSum=Math.max(num,preSum+num);
            maxSum=Math.max(maxSum,preSum);
        }
        return maxSum;
    }
    public static int maxSubArray2(int[] nums) {
        if (nums.length == 1) {
            return nums[0];
        }
        int maxSum = Integer.MIN_VALUE;
        int left = 0;
        int right = 0;
        int preSum = 0;
        while (left <= right && right < nums.length) {
            preSum += nums[right++];
            while ((preSum < 0 || nums[left] < 0) && left + 1 < right) {
                preSum -= nums[left];
                left++;
            }
            maxSum = Math.max(maxSum, preSum);
        }
        return maxSum;
    }

}
